題目

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

題意

從陣列中，找出超過半數的元素。

Example 1:

Input: [3,2,3]
Output: 3

Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2

解題想法

這題可以用一種解法，叫做摩爾投票法(Moore voting)，也叫多數投票法。
它的原理是，相鄰的元素做比較，若不相等，將它們從陣列中剔除，如此一來最後剩下的，就會是最多數的，因為有超過半數的保證。
作法：
宣告變數majority為陣列的第一個元素，計數器count初始為0，
遍歷陣列，元素相等count+1，不相等count-1，
當count=0表示最多元素將會替換，遍歷完後，最後majority中的元素，將是最多數的元素。

Solution

var majorityElement = function(nums) {
let count = 1, majority = nums[0];
  for (let i = 1; i < nums.length; i++) {
    if (count === 0) {
      majority = nums[i];
    }
    if (majority === nums[i]) {
      count++;
    } else {
      count--;
    }
  }
  return majority;
};